package zw_1_100.zw_69_x的平方根;

/**
 * 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
 * <p>
 * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
 * <p>
 * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：x = 4
 * 输出：2
 * 示例 2：
 * <p>
 * 输入：x = 8
 * 输出：2
 * 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
 *  
 * <p>
 * 提示：
 * <p>
 * 0 <= x <= 231 - 1
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/sqrtx
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */


class Solution {
    public static void main(String[] args) {
        int mySqrt = mySqrt(123);
        System.out.println(mySqrt);
    }

    /**
     * 二分法
     * 时间复杂度：O(logx)，每一次搜索的区间大小约为原来的 1/2,时间复杂度为 O(log2(x))=O(logx)；空间复杂度：O(1)。
     * @param x
     * @return
     */
    public static int mySqrt(int x) {
        // 特殊值判断
        if (x == 0 || x == 1) return x;
        int left = 1;
        int right = x / 2;
        // 在区间 [left..right] 查找目标元素
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            // 注意：这里为了避免乘法溢出，改用除法
            if (mid > x / mid) {
                // 下一轮搜索区间是 [left..mid - 1]
                right = mid - 1;
            } else {
                // 下一轮搜索区间是 [mid..right]
                left = mid;
            }
        }
        return left;
    }


    /**
     * 牛顿法
     * x(k+1) = [x(k)+a/x(k)]/2
     * @param x
     * @return
     */
//    public static int mySqrt(int x) {
//        long a = x;
//        while (a * a > x){
//            a = (a + x / a) / 2;
//        }
//        return (int) a;
//    }
}